Récurrence forte

Le principe de récurrence forte s'énonce comme suit.

Soit  `P_n` une propriété dépendant de l'entier naturel `n` . Supposons que :

• il existe un entier  `n_0` tel que  `P_{n_0}` est vraie (initialisation) ;
  
• pour tout entier \(n \geqslant n_0\) , si    \(P_{n_0}\) ,  \(P_{n_0+1}\) , ...,  `P_n`  sont vraies, alors   `P_{n+1}` est vraie (hérédité).
  

Alors,  `P_n` est vraie pour tout entier naturel \(n \geqslant n_0\) .

Exercice 1

Soit \(\left(u_{n}\right)\)  la suite définie par :  `u_0=1`  et \(\forall n\in\mathbb{N}\) ,  `u_{n+1}=\underset{k=0}{\overset{n}{\sum}}u_{k}` . Démontrer que \(\forall n\in\mathbb{N}^{*}, u_{n}=2^{n-1}\) .

Exercice 2

1. Démontrer que tout entier naturel non nul s'écrit comme un produit d'une puissance de 2 et d'un nombre impair, c'est-à-dire  \(\forall n\in\mathbb{N}^*,\)   \(\exists\left(p,q\right)\in\mathbb{N}^{2}\)  ; \(n=2^{p}\left(2q+1\right)\) .
2. Cette décomposition est-elle unique ?